1. Field of the Invention
The invention relates to the field of communication. More specifically, the invention relates to communication networks.
2. Background of the Invention
A router hosts a routing protocol(s) that can include one or more of the following: the Routing Information Protocol (RIP), the Interior Gateway Protocol (IGP), the Border Gateway Protocol (BGP), the Exterior Gateway Protocol (EGP), Open Short Path First (OSPF), Intermediate System to Intermediate System (IS-IS), etc. A router exchanges messages with neighboring routers in accordance with one or more of the hosted routing protocols. These messages are used to maintain a table of routing information (“routing table”). A routing table stores the state of the network topology and the best-known route to destinations. A given routing table can include route information for hundreds of thousands of routes. Route information typically includes a destination network prefix, an Internet Protocol (IP) address for a next hop, an outgoing physical interface or port number, metrics of the route, etc.
FIG. 1 (Prior Art) is a diagram illustrating a routing table. The routing table is comprised of multiple columns. The routing table 100 illustrated in FIG. 1 identifies destinations in the first column of the routing table 100. In the second column of the routing table 100, addresses for next hops corresponding to the destinations in the first column are identified. In the third column of the routing table 100, interfaces corresponding to the next hops in the second column are identified. A given row of the routing table 100 describes a path to the destination identified in the first column of the given row.
In the routing table 100 illustrated in FIG. 1, rows 1-3 of the routing table 100 identify destinations A, B, and C. The next hop in the paths to the destinations A-C is a network element X as indicated in the routing table 100. The interface for the next hop X is the interface 1 as indicated in the third column of rows 1-3 of the routing table 100. The last two rows of the routing table 100 identify a next hop Z for destinations M and N. The last two rows identify an interface 3 as the interface corresponding to the next hop Z.
At startup, a given router, which hosts the routing table 100, downloads the routing table 100 into each of the router's line cards. The given router may download the entire routing table 100, or selected columns from the routing table 100. A single route to each destination in the routing table 100 is downloaded into each line card. Typically, a router downloads the next hop and interface for each destination in the routing table 100 for each of its line cards as a forwarding table.
FIG. 2 (Prior Art) is a forwarding table. Line cards host forwarding tables in order to remove from the central processing unit the intensive task of processing traffic. When a given one of a router's line cards receives traffic, the line card processes the traffic to determine the traffic's destination and forwards the traffic to the corresponding next hop via the outgoing physical interface indicated by the line card's forwarding table. For example, a line card that receives traffic destined for the network element A, processes the packet at each layer (i.e. each header) until reaching the layer 3 header to determine the packet's layer 3 destination. After determining the packet's layer 3 destination, the layer 3 destination is looked up in the forwarding table. From the forwarding table, the process determines how to forward the packet in order to transmit the packet to its destination.